#include <iostream>
#include <algorithm>
#include <vector> 
#include <queue>

typedef long long ll;
using namespace std;


//class Solution {
//public:
//    vector<int> replaceElements(vector<int>& arr) {
//        int n = arr.size();
//        vector<int> ans(n);
//        int tmp = arr[n - 1];
//        ans[n - 1] = -1;
//        for (int i = n - 2; i >= 0; i--) {
//            ans[i] = tmp;
//            if (arr[i] > tmp)
//                tmp = arr[i];
//        }
//        return ans;
//    }
//};

//int t, m;
//int tm[105];
//int val[105];
//int dp[1005];
//
//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    cin >> t >> m;
//    for (int i = 1; i <= m; i++) {
//        cin >> tm[i] >> val[i];
//    }
//    for (int i = 1; i <= m; i++) {
//        for (int j = t; j >= tm[i]; j--) {
//            dp[j] = max(dp[j - tm[i]]+val[i], dp[j]);
//        }
//    }
//    cout << dp[t];
//
//    return 0;
//}

//int n, m;
//int king[65], fans[65], follows[65][2];
//int cost[65], val[65];
//int dp[32005];
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> m;
//	for (int i = 1,v,p,q; i <= m; i++) {
//		cin >> v >> p >> q;
//		cost[i] = v;
//		val[i] = v * p;
//		if (!q) {
//			king[i] = 1;
//		}
//		else {
//			follows[q][fans[q]++] = i;
//		}
//	}
//	int p = 0;
//	for (int i = 1,fan1,fan2; i <= m; i++) {
//		if (king[i]) {
//			for (int j = n; j >= cost[i]; j--) {
//				dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
//				fan1 = fans[i] >= 1 ? follows[i][0] : -1;
//				fan2 = fans[i] >= 2 ? follows[i][1] : -1;
//				if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
//					dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
//				}
//				if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
//					dp[j] = max(dp[j], dp[j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
//				}
//				if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2]>=0) {
//					dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
//				}
//			}
//		}
//	}
//	cout<<dp[n];
//
//
//
//	return 0;
//}


//struct node {
//	int v;
//	bool operator<(const node& x)const{
//		return x.v < v;
//	}
//};
//
//priority_queue<node> q;
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	for (int i = 0; i <= 10; i++) {
//		q.push({ i });
//	}
//	while (!q.empty()) {
//		cout << q.top().v << ' ';
//		q.pop();
//	}
//	return 0;
//}

//struct node {
//	int index;
//	ll su;
//	bool operator<(const node& x)const {
//		return x.su < su;
//	}
//};
//
//priority_queue<node> q;
//
//int nums[105];
//int n, k;
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n>>k;
//	for (int i = 0; i < n; i++) {
//		cin >> nums[i];
//	}
//	q.push({ 0,nums[0] });
//	vector<int> ans(k);
//	for (int i = 1; i < k; i++) {
//		auto cur = q.top();
//		q.pop();
//		ans[i] = cur.su;
//		ll sum = cur.su;
//		int last = cur.index;
//		if (last + 1 < n) {
//			q.push({ last + 1,sum - nums[last] + nums[last + 1] });
//			q.push({ last + 1,sum + nums[last + 1] });
//		}
//	}
//
//	return 0;
//}


//int n, m, w;
//int cost[10005], val[10005], f[10005];
//int dp[10005];
//
//int find(int x) {
//	return f[x] == x ? x : f[x] = find(f[x]);
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> m >> w;
//	for (int i = 1; i <= n; i++) {
//		cin >> cost[i] >> val[i];
//		f[i] = i;
//	}
//	for (int i = 1,u,v; i <= m; i++) {
//		cin >> u >> v;
//		int fu = find(u), fv = find(v);
//		f[fu] = fv;
//	}
//	for (int i = 1; i <= n; i++) {
//		if(f[i]!=i) {
//			val[find(i)] += val[i];
//			cost[find(i)] += cost[i];
//		}
//	}
//
//	for (int i = 1; i <= n; i++) {
//		if(f[i]==i)
//		for (int j = w; j >= cost[i]; j--) {
//			dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
//		}
//	}
//	cout << dp[w];
//	return 0;
//}

